package 题目集.dfs.图;

import org.junit.Test;
import 题目集.拓扑排序.ch02_喧闹和富有;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 给你一个边数组，一个点数组
 * 问对于每个点，找到能抵达它的最小值。输出这些最小值的编号
 * https://leetcode.cn/problems/loud-and-rich/description/
 */
public class ch04_喧闹和富有 {
    /**
     * dfs思路：
     *      反向建边，然后dfs+记忆化找到最小的编号
     * 拓扑排序思路：{@link ch02_喧闹和富有}
     */
    List<Integer>[] graph;
    int[] quiet;
    int[] dp;
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        this.quiet = quiet;
        dp = new int[quiet.length];
        Arrays.fill(dp,-1);
        graph = new List[quiet.length];
        for (int i = 0; i < quiet.length; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int[] r : richer) {
            graph[r[1]].add(r[0]);  //反向建边
        }
        int[] res = new int[quiet.length];
        for (int i = 0; i < quiet.length; i++) {
            res[i] = dfs(i);
        }
        return res;
    }

    private int dfs(int i) {
        if (dp[i]!=-1) {
            return dp[i];
        }
        int res=i;
        for (Integer to : graph[i]) {
            int nextI = dfs(to);
            if (quiet[res]>quiet[nextI]) {
                res=nextI;
            }
        }
        dp[i]=res;
        return dp[i];
    }
    @Test
    public void test(){
        int[][] richer = {{1,0},{2,1},{3,1},{3,7},{4,3},{5,3},{6,3}};
        int[] quiet = {3,2,5,4,6,1,7,0};
        int[] res = loudAndRich(richer, quiet);
        for (int re : res) {
            System.out.print(re+" ");
        }
    }
}
